package com.peng.leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * IsValidBST
 * <p>
 * 面试题 04.05. 合法二叉搜索树
 *
 * @author: lupeng6
 * @create: 2021/2/5 11:36
 */
public class IsValidBST {

    public static void main(String[] args) {
        Integer[] arr = {10, 5, 15, null, null, 6, 20};
        TreeNode treeNode = TreeMain.array2tree(arr);
        System.out.println(new IsValidBST().isValidBST(treeNode));
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return inOrder(root, new ArrayList<>());
    }

    boolean inOrder(TreeNode node, List<Integer> values) {
        if (node.left != null) {
            boolean flag = inOrder(node.left, values);
            if (!flag) {
                return false;
            }
        }
        int val = node.val;
        if (!values.isEmpty() && values.get(values.size() - 1) >= val) {
            return false;
        }
        values.add(val);
        if (node.right != null) {
            boolean flag = inOrder(node.right, values);
            if (!flag) {
                return false;
            }
        }
        return true;
    }

}
